#include <iostream>
#include <string>
#include <cstring>
using namespace std;

void inline swap(int &a, int &b){int temp = a;a = b;b = temp;}

int partitionI(int a[], int l, int h){
    int m = l+1;
    for(int i=m; i<=h; i++) {
        if(a[i]<a[l]){
            if(m!=i) swap(a[i], a[m]);
            m++;
        }
    }
    if(l!=m-1) swap(a[l],a[m-1]);
    return m-1;
}

int partitionII(int a[], int l, int h){
    int k = a[l];
    while(l<h) {
        while(l<h && a[h]>=k) h--;
        a[l] = a[h];
        while(l<h && a[l]<k) l++;
        a[h] = a[l];
    }
    a[h] = k;
    return h;
}

void qsort(int a[], int l, int h)
{
    if(l>=h) return;
    int mid = partitionI(a, l, h);
    qsort(a, l, mid-1);
    qsort(a, mid+1, h);
}

void quick_sort(int a[], int n){
    if(n == 1) return;
    qsort(a, 0, n-1);
}

void print(int a[], int n) {
    for(int i=0; i<n; i++) cout << a[i] <<" ";
    cout << endl;
}

int main()
{
    int a[] = {2,1,5,4,212,78,1,0,2,3,4,5};
    int n = sizeof(a)/sizeof(int);
    print(a,n);
    quick_sort(a,n);
    print(a,n);
    return 0;
}
